#!/usr/env python

#  Copyright (c) 2008 Gregory Andrew Robinson
#  gregarobi@dev.java.net
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.

from string import maketrans

class ComboItem:
  def __init__(self, combo, words):
    self.combo = combo
    self.words = words

class RankItem:
  def __init__(self, rank, comboitems):
    assert isinstance(comboitems[0], ComboItem)
    self.rank = rank
    self.combos = comboitems

def chardelta(word1, word2):
  delta = 0
  for i in xrange(len(word1)):
    if word1[i] == word2[i]:
      delta += 1
  return delta

class Challenge:

  def __init__(self):
    self.words = {}
    self.numcombos  = {}
    self.makecombolist = lambda : [ ComboItem(combo, words) for (combo, words) in self.numcombos.iteritems()]
    self.is_not_unique = lambda comboitem : len(comboitem.words) > 1
    letters = 'abcdefghijklmnopqrstuvwxyz'
    numbers = '22233344455566677778889999'
    transtable = maketrans(letters, numbers)
    self.getnumbers = lambda word : word.translate(transtable)

  def diff2chars(self, comboitem):
    words = comboitem.words[:]
    goodwords = []
    while len(words) > 0:
      word1 = words.pop()
      simmatch = False
      for j, word2 in enumerate(words):
        if chardelta(word1, word2) > 1:
          words.pop(j)
          simmatch = True
      if not simmatch:
        goodwords.append(word1)
    return ComboItem(comboitem.combo, goodwords)


  def greatest(self, a, b):
    if a.rank > b.rank:
      return a
    elif a.rank < b.rank:
      return b
    else:
      # Combine combos of similar rank
      return RankItem( a.rank, a.combos + b.combos )

  def addwords(self, wordlist):
    for line in wordlist:
      line = line.strip()
      if line.isalpha():
        word = line.lower()
        numcombo = self.getnumbers(word)

        # Add the word to the words dictionary
##        self.words.update( {word : getnumbers(word)} )

        # Create a list to add to the combos dictionary
        entry = [word]
        # Add any existing words to the entry
        if numcombo in self.numcombos:
          entry += self.numcombos[numcombo]
        # Replace or add the combo's dictionary entry
        self.numcombos.update( {numcombo : entry} )
    self.combolist = self.makecombolist()

  def getlongest(self):
    # Map to word lengths
    mapwordlen = lambda comboitem : RankItem( len(comboitem.combo), [comboitem])
    return reduce(self.greatest,
           map(mapwordlen,
           filter(self.is_not_unique,
           map(self.diff2chars,
           filter(self.is_not_unique, self.combolist[:])))))

  # A programmer's most-needed function
  # But really it returns the combos with the most 
  def getpopular(self):
    # Map to get lengths
    mappopular = lambda comboitem : RankItem( len(comboitem.words), [comboitem])
    return reduce(self.greatest,
           map(mappopular,
           filter(self.is_not_unique, self.combolist[:])))

def main():
  t = Challenge()
  wordlist = open('words')

#  Debugging line
#  wordlist = ['aa', 'bb', 'cc', 'd', 'e', 'qqqqq', 'rrrrr', 'qqqqqq', 'qqqqqr']

  t.addwords(wordlist)

  longest = t.getlongest()
  print 'longest:'
  for combo in longest.combos:
    print '  ', combo.combo
    for word in combo.words:
      print '    ', word
  popular = t.getpopular()
  print 'popular'
  for combo in popular.combos:
    print '  ', combo.combo
    for word in combo.words:
      print '    ', word

if __name__ == '__main__':
  main()
